package NowCoder.Mathematics;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/70e00e490b454006976c1fdf47f155d9
 * 来源：牛客网
 * 最近公共祖先
 * 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
 * 将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。
 * 现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
 *
 * 测试样例：
 * 2，3
 * 返回：1
 */
public class 最近公共祖先_编程_1_5_19 {
    //TODO:请重新做这一道题
    public int getLCA(int a, int b) {
        // write code here
        //因为是一颗满二叉树，他的编号是按照一层一层 从左往右进行编号
        //即 该编号方式是层序遍历
        //所以当一个结点为x ，然后他的双亲结点是 x / 2
        while(a != b){
            if(a > b){
                a /= 2;
            }else{
                b /= 2;
            }
        }
        return a;
    }
}
